#include <iostream>
#include <cmath>
#include <opencv4/opencv2/opencv.hpp>
#include <time.h>
using namespace std;
using namespace cv;
//求两个向量的点乘，输入为四个点坐标，第1、3个点为向量的起始点
/*double VecPoMul(double x1,double y1,double x2,double y2,double x3,double y3,double x4,double y4)
{
    return ((x4-x3)*(x2-x1)+(y4-y3)*(y2-y1));
}*/
//求两个向量的叉乘，输入为四个点坐标，第1、3个点为向量的起始点
int VecCrMul(int x1,int y1,int x2,int y2,int x3,int y3,int x4,int y4)
{
    return ((x4-x3)*(y2-y1) - (y4-y3)*(x2-x1));
}

int main() {
    while(true) {
        //const double PI=16*atan((double)1/5)-4*atan((double)1/239);
        //获取计算机从开机到程序开始的计时周期数
        long long time_start=clock();
        //创建画纸（因为不太会用三通道的矩阵所以直接读取了一张jpg图片，图片的长宽被处理过，现在为600x400，为BGR图片）
        Mat picture = imread("../Image/1.jpg");
        //创建随机生成器
        RNG rng((unsigned) time(NULL));
        //创建需要的四个点（后续称为pt0、pt1、pt2、pt3）、及用于储存临时的Point值的变量
        Point pt[4],pt_temp;
        //用于储存临时的bool值的变量
        bool bl_temp=true;
        //点到直线的最短距离，以及储存的临时距离
        double len,len_temp;
        //三条直线的直线方程的ABC三个值
        double A[3],B[3],C[3];
        //生成所需的四个随机点
        for (int i = 0; i < 4; i++) {
            //用rng随即生成点的坐标
            if(i==0||i==3)
                pt[i].x = rng.uniform(1 , 598), pt[i].y = rng.uniform(1 , 398);
            else
                pt[i].x = rng.uniform(0 , 599), pt[i].y = rng.uniform(0 , 399);
            if (i == 2) {
                //用线段的斜率以及向量乘法避免线段重叠（||后面的部分）或者成为不需要的直角（||前面的部分）
                while (((pt[i - 2].x - pt[i - 1].x) * (pt[i].x - pt[i - 1].x) +
                        (pt[i - 2].y - pt[i - 1].y) * (pt[i].y - pt[i - 1].y) == 0) ||
                       ((pt[i - 2].x - pt[i - 1].x) * (pt[i - 1].y - pt[i].y) ==
                        (pt[i - 2].y - pt[i - 1].y) * (pt[i - 1].x - pt[i].x))) {
                    //如果符合while条件即不符合题目要求，则再取一次值
                    pt[i].x = rng.uniform(1 , 599), pt[i].y = rng.uniform(1 , 399);
                }
            }
            if (i == 3) {
                //为临时bool变量赋值，！bl_temp在此后表示第一、三条射线有交点
                bl_temp= false;
                //用向量乘法计算，使得两个角一个是锐角一个是钝角，除以一百防止其超过int的限制，同时用bl_temp防止射线相交
                while ((((pt[i - 3].x - pt[i - 2].x) * (pt[i - 1].x - pt[i - 2].x) / 100 +
                        (pt[i - 3].y - pt[i - 2].y) * (pt[i - 1].y - pt[i - 2].y) / 100) *
                       ((pt[i - 2].x - pt[i - 1].x) * (pt[i].x - pt[i - 1].x) / 100 +
                        (pt[i - 2].y - pt[i - 1].y) * (pt[i].y - pt[i - 1].y) / 100) > 0)||
                                !bl_temp) {
                    pt[i].x = rng.uniform(1 , 599), pt[i].y = rng.uniform(1 , 399);
                    //求得此时四点组成的三条直线的直线方程参数ABC
                    for(int k=0;k<3;k++){
                        if(pt[k].x - pt[k + 1].x != 0){
                            A[k]=-((double)pt[k].y - (double)pt[k+1].y)/((double)pt[k].x - (double)pt[k + 1].x);
                            B[k]=1;
                            C[k]=-(A[k]*((double)pt[k].x+(double)pt[k + 1].x) + ((double)pt[k].y + (double)pt[k + 1].y)) / 2;
                        }
                        else{
                            A[k] = 1;
                            B[k] = 0;
                            C[k] = - (double)pt[k].x;
                        }
                    }
                    //通过行列式解出第一、三条直线的交点
                    pt_temp.x=(-(double)C[0]+(double)C[2])/((double)A[0]-(double)A[2]),pt_temp.y=(int)((-(double)C[2]*(double)A[0]+(double)C[0]*(double)A[2])/((double)A[0]-(double)A[2]));
                    //通过Ax0+By0+C大于或者小于0确定，如果该交点与pt0和pt3在第二条直线的同一侧，那么一定是射线相交，则重新取一次
                    if((((double)A[1]*pt_temp.x+(double)B[1]*pt_temp.y+(double)C[1])/10000)*(((double)A[1]*pt[0].x+(double)B[1]*pt[0].y+(double)C[1])/10000)>0 &&
                            (((double)A[1]*pt_temp.x+(double)B[1]*pt_temp.y+(double)C[1])/10000)*(((double)A[1]*pt[3].x+(double)B[1]*pt[3].y+(double)C[1])/10000)>0 ){
                        bl_temp=false;
                    }
                    else
                        bl_temp=true;
                }
            }
        }
        //开始遍历
        for(int i=0;i<400;i++){
            for(int j=0;j<600;j++){
                //初始化len为一个绝对大的值
                len=1023;
                for(int m=0;m<3;m++){
                    //与第一条直线（射线）的最短距离
                    if(m==0){
                        //点乘小于0，在射线的点的一侧，距离为到点pt1的距离
                        if(((pt[0].x - pt[1].x) * (j - pt[1].x) + (pt[0].y - pt[1].y) * (i - pt[1].y)) < 0)
                            len_temp=sqrt(pow(i-pt[1].y,2)+pow(j-pt[1].x,2));
                        else//否则距离为颠倒直线的距离公式求出来的值
                            len_temp=((double)A[0]*j+(double)B[0]*i+(double)C[0])/(sqrt((pow((double)A[0],2)+pow((double)B[0],2))));
                        if(abs(len)>abs(len_temp)) {//如果有更小的距离
                            if (VecCrMul(pt[1].x,pt[1].y,pt[0].x,pt[0].y,pt[1].x,pt[1].y,j,i) <= 0)//叉乘，结果小于零在顺时针方向
                                len = abs(len_temp);
                            if(VecCrMul(pt[1].x,pt[1].y,pt[0].x,pt[0].y,pt[1].x,pt[1].y,j,i) > 0)//大于零在逆时针方向
                                len = -abs(len_temp);
                        }
                    }
                    if(m==1){
                        //在pt2外的一侧时
                        if(((pt[1].x - pt[2].x) * (j - pt[2].x) + (pt[1].y - pt[2].y) * (i - pt[2].y)) < 0){
                            len_temp= sqrt(pow(i-pt[2].y,2)+pow(j-pt[2].x,2));//计算点到点的距离
                        }
                        else if(((pt[2].x - pt[1].x) * (j - pt[1].x) + (pt[2].y - pt[1].y) * (i - pt[1].y)) < 0)//在pt1外的一侧时
                            len_temp= sqrt(pow(i-pt[1].y,2)+pow(j-pt[1].x,2));//计算点到点的距离
                        else//在pt2与pt1之间时
                            len_temp=((double)A[1]*j+(double)B[1]*i+(double)C[1])/(sqrt((pow((double)A[1],2)+pow((double)B[1],2))));//计算点到线的距离
                        if(VecCrMul(pt[1].x, pt[1].y, pt[2].x, pt[2].y, pt[1].x, pt[1].y, pt[0].x, pt[0].y) < 0)//判断线段的左右关系，在readme文件中多次染色法的说明中，左右关系会影响染色顺序（是红-蓝-红还是蓝-红-蓝）
                        {
                            if(abs(len) >= abs(len_temp)) {
                                //只有当此时这个点到这条线的距离最短的时候才参与染色（避免一次染色操作之后将之前全部的覆盖，且当点到这个线的距离最短时，也就是这个点的有向距离的正负由这个线负责）
                                //多次染色思路见readme文件
                                //染色，用len的数字正负标记是红色还是是蓝色
                                if (VecCrMul(pt[2].x, pt[2].y, pt[1].x, pt[1].y, pt[2].x, pt[2].y, j, i) <= 0)
                                    len = abs(len_temp);
                                if(VecCrMul(pt[2].x, pt[2].y, pt[1].x,pt[1].y, pt[2].x, pt[2].y, j, i) > 0)
                                    len = -abs(len_temp);
                                if (VecCrMul(pt[1].x,pt[1].y,pt[0].x,pt[0].y,pt[1].x,pt[1].y,j,i) < 0)
                                    len = abs(len_temp);
                            }
                        }
                        else
                        {
                            if(abs(len) >= abs(len_temp)) {
                                if(VecCrMul(pt[2].x, pt[2].y, pt[1].x, pt[1].y, pt[2].x, pt[2].y, j, i) > 0)
                                    len = -abs(len_temp);
                                if (VecCrMul(pt[2].x, pt[2].y, pt[1].x, pt[1].y, pt[2].x, pt[2].y,j, i) <= 0)
                                    len = abs(len_temp);
                                if(VecCrMul(pt[1].x,pt[1].y,pt[0].x,pt[0].y,pt[1].x,pt[1].y,j,i) > 0)
                                    len = -abs(len_temp);
                            }
                        }
                    }
                    if(m==2){
                        if(((pt[3].x - pt[2].x) * (j - pt[2].x) + (pt[3].y - pt[2].y) * (i - pt[2].y)) < 0)//在pt3外时
                            len_temp= sqrt(pow(i-pt[2].y,2)+pow(j-pt[2].x,2));//计算点到点的距离
                        else//在pt3内时
                            len_temp=((double)A[2]*j+(double)B[2]*i+(double)C[2])/(sqrt(pow((double)A[2],2)+pow((double)B[2],2)));//计算点到线段的距离
                        if(VecCrMul(pt[2].x, pt[2].y, pt[3].x, pt[3].y, pt[2].x, pt[2].y, pt[1].x, pt[1].y)<0)
                        {
                            if(abs(len) >= abs(len_temp)) {//染色
                                if (VecCrMul(pt[3].x, pt[3].y, pt[2].x, pt[2].y, pt[3].x, pt[3].y, j, i) <= 0)
                                    len = abs(len_temp);
                                if(VecCrMul(pt[3].x, pt[3].y, pt[2].x, pt[2].y, pt[3].x, pt[3].y, j, i) > 0)
                                    len = -abs(len_temp);
                                if (VecCrMul(pt[2].x,pt[2].y,pt[1].x,pt[1].y,pt[2].x,pt[2].y,j,i) <= 0)
                                    len = abs(len_temp);
                                //若为Z字型，则需要再次染色一圈，原理可以参照多次染色思路自行推导，可以解决Z字型为第一个钝角加第二个极小锐角时的bug
                                if((((double)A[1]*pt[0].x+(double)B[1]*pt[0].y+(double)C[1])/10000)*(((double)A[1]*pt[3].x+(double)B[1]*pt[3].y+(double)C[1])/10000)<0){
                                    if(VecCrMul(pt[1].x,pt[1].y,pt[0].x,pt[0].y,pt[1].x,pt[1].y,j,i) > 0)
                                        len = -abs(len_temp);
                                    if (VecCrMul(pt[3].x, pt[3].y, pt[2].x, pt[2].y, pt[3].x, pt[3].y, j, i) <= 0)
                                        len = abs(len_temp);
                                }
                            }
                        }
                        else
                        {
                            if(abs(len) >= abs(len_temp)) {//染色
                                if(VecCrMul(pt[3].x, pt[3].y, pt[2].x, pt[2].y, pt[3].x, pt[3].y, j, i) > 0)
                                    len = -abs(len_temp);
                                if (VecCrMul(pt[3].x, pt[3].y, pt[2].x, pt[2].y, pt[3].x, pt[3].y, j, i) <= 0)
                                    len = abs(len_temp);
                                if(VecCrMul(pt[2].x, pt[2].y, pt[1].x, pt[1].y, pt[2].x, pt[2].y, j, i) > 0)
                                    len = -abs(len_temp);
                                if((((double)A[1]*pt[0].x+(double)B[1]*pt[0].y+(double)C[1])/10000)*(((double)A[1]*pt[3].x+(double)B[1]*pt[3].y+(double)C[1])/10000)<0){
                                    if (VecCrMul(pt[1].x, pt[1].y, pt[0].x, pt[0].y, pt[1].x, pt[1].y, j, i) <= 0)
                                        len = abs(len_temp);
                                    if (VecCrMul(pt[3].x, pt[3].y, pt[2].x, pt[2].y, pt[3].x, pt[3].y, j, i) > 0)
                                        len = -abs(len_temp);
                                }
                            }
                        }
                    }
                }
                //进行真正意义的染色，如果len大于等于0，为红色（因为是BGR不是RGB），len小于0，为蓝色
                if(len>=0)
                {
                    picture.at<Vec3b>(i, j)[0] = 255-len/3;
                    picture.at<Vec3b>(i, j)[1] = 255-len/3;
                    picture.at<Vec3b>(i, j)[2] = 255;
                }
                else
                {
                    picture.at<Vec3b>(i, j)[0] = 255;
                    picture.at<Vec3b>(i, j)[1] = 255+len/3;
                    picture.at<Vec3b>(i, j)[2] = 255+len/3;
                }
            }
        }
        //生成随机点连接成的折线段
        for (int i = 0; i < 3;line(picture, pt[i], pt[i + 1], Scalar (0,0,0), 1),i++) {}
        //展示结果的图片
        imshow("结果图片", picture);
        //获取从开机到程序结束的时候计时周期数
        long long time_end=clock();
        //输出单位为毫秒的运行时间，CLOCKS_PER_SEC为表达运行周期数的常量（单位为 运行周期/s）
        cout<<"time="<<((double)(time_end-time_start))/CLOCKS_PER_SEC*1000<<"ms"<<endl;
        //输入一个字符，没输入的话先等待
        char Key= (char)waitKey(0);
        //如果输入的不是r，break出循环，程序结束，假如是r，再次执行程序，生成一张图片
        if(Key != 'r')
            break;
    }
}
